package primary.primary0;

/**
 * 数组，dfs + 回溯
 */
public class S0079单词搜索 {

    /**
     * 50,72
     * 就是dfs，以每个节点为开始往后找
     */
    class Solution {
        public boolean exist(char[][] board, String word) {
            boolean[][] visited = new boolean[board.length][board[0].length];
            for(int i = 0; i < board.length; i ++){
                for(int j = 0; j < board[0].length; j++){
                    if(dfs(board, visited, word, 0, i, j)){
                        return true;
                    }
                }
            }
            return false;
        }


        public boolean dfs(char[][] board, boolean[][] visited, String word, int loc, int m, int n){
            if(loc >= word.length()){
                // 时刻注意结束条件，这个一开始还搞错了
                return true;
            }
            if(m < 0 || n < 0 || m >= board.length || n >= board[0].length || visited[m][n] ){
                return false;
            }
            if(board[m][n] != word.charAt(loc)){
                return false;
            }
            // 当前值吻合，往下走，要注意这个visited的复原
            visited[m][n] = true;
            boolean res = dfs(board, visited, word, loc + 1,m + 1, n) || dfs(board, visited, word, loc + 1,m - 1, n)
                    || dfs(board, visited, word, loc + 1,m, n + 1) || dfs(board, visited, word, loc + 1, m, n - 1);
            visited[m][n] = false;
            return res;
        }
    }
}
